Count and Say || Balanced Binary Tree

发表于

Count and Say

Question

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Analysis

两个StringBuilder:pre/cur保存需要被描述的字符串和当前的字符串

  • count每次计数应该从1开始，因为不可能出现0个的元素
  • 在对一个字符串循环查数结束后，需要current.append(count).append(tmp)由于此时最后一个（一种）字符还没有加入字符串中

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public String countAndSay(int n) {
        StringBuilder cur=new StringBuilder("1");
        StringBuilder pre;
        for(int i=1;i<n;i++){
            int count=1;
            pre=cur;
            cur=new StringBuilder();
            char tmp=pre.charAt(0);
            for(int j=1,len=pre.length();j<len;j++){
                if(pre.charAt(j)!=tmp){
                    cur.append(count).append(tmp);
                    count=1;
                    tmp=pre.charAt(j);
                }
                else
                    count++;
            }
            cur.append(count).append(tmp);
        }
        return cur.toString();
    }
}

Balanced Binary Tree

Question

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Analysis

https://discuss.leetcode.com/topic/7798/the-bottom-up-o-n-solution-would-be-better/2

Code

Original Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    boolean res=true;
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return res;
        DFS(root);
        return res;
    }
    
    private void DFS(TreeNode root){
        if(root==null)
            return;
        if(Math.abs(getheight(root.left)-getheight(root.right))>1)
            res=false;
        if(root.left!=null)
            DFS(root.left);
        if(root.right!=null)
            DFS(root.right);
    }
    
    private int getheight(TreeNode node){
        if(node==null)
            return 0;
        return Math.max(getheight(node.right),getheight(node.left))+1;
    }
}
Top-Down Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null)
            return true;
        int height=Math.abs(depth(root.left)-depth(root.right));
        return height<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    
    private int depth(TreeNode node){
        if(node==null)
            return 0;
        return Math.max(depth(node.left),depth(node.right))+1;
    }
}
Down-Top Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return DFS(root)!=-1;
    }
    
    private int DFS(TreeNode root){
        if(root==null)
            return 0;
        int lh=DFS(root.left);
        if(lh==-1)   return -1;
        int rh=DFS(root.right);
        if(rh==-1)   return -1;
        if(Math.abs(lh-rh)>1)   return -1;
        return Math.max(DFS(root.left),DFS(root.right))+1;
    }
}